/*  slflldiv.cpp  by K.Tsuru  */
// function ID = 216, 217 DRADIX, BRADIX
/************************************************************
SLong and SInteger class
It provides a quotient m/n and a remainder m%n.
Depending on the value of "pfLLDiv" the used method is Knuth
or Newton.
*************************************************************/
#ifndef SN_H
#include "sn.h"
#endif
// static objects of SLong class
int SLong::llDivMode = SLong::reset;

static const char* const func = "LLDiv";
// m = n*q + r, verifying function
static void DivVerify(const SLong& m, const SLong& n, const Ldiv_t& r){
    const char* const divfunc = (SLong::LLDivMode() == m.Knuth) ? "KnuthLLDiv" : "NewtonLLDiv";
    SLong t;
    int c = LLCompare(n, r.rem), err;   //Must be c > 0 (|n| > |r.rem|).
    if( c <= 0 ) err = 1;   // r < n ?
    else {
        SLong t;
        t = m - r.quot*n - r.rem;   //t must be equal to zero.
        err = t.Sign(216);
    }
    if(err) SNManager::SetError(m.VERIFY, divfunc, 216);
}
//m/n, The number of figures of n is two or under.
static int DivByShort(const SLong& m, const SLong& n, Ldiv_t& r){
    ulong d = n.Low2(); //d=n(1)*radix+n(0)
    if( d <= m.SlOpMaxValue() ){    //multi-precision integer/short integer
        long rem = 0;
        // r.quot = m/|n|
        if(d > 1uL) r.quot = LsDiv( m, d, &rem);//r.quot has tha same type as m.
        else        r.quot = m; // |n| = 1, rem = 0;
        if(n.Sign() < 0) r.quot.ChangeSign();   // quot != 0, d>0, n<0
        r.rem.SetLong(rem); //The sign of "r.rem" is the same as that of "m",
                            //which is considered in LsDiv() for "rem".
        return 1;
    }
    return 0;
}
Ldiv_t LLDiv(const SLong& m, const SLong& n, bool needRem){
    //If "verify" is ON it calcutates the remainder.
    if(SNManager::Verify() == ON) needRem = true;
    if( !n.Sign() ) m.SetError(m.DIVIDED_BY_ZERO, func, 216);   // n=0
    int c = LLCompare(m, n);             //comparing the largeness
    int sgn = m.Sign(216)*n.Sign(216);   //the sign of quotient

    Ldiv_t result;
    result.quot.SetType(m.Type());  result.rem.SetType(m.Type());
// |n| > 0
    if(c < 0){  // 0=< |m| < |n|  quotient=0, remainder=m
        result.quot.SetZero();  result.rem = m;
    } else if(c == 0){  // |m| = |n| (!= 0)
        result.quot = sgn;  result.rem.SetZero();
    }
    if(c <= 0) return result;
// |m| > |n|
    if( (n.aHead > 0) && ( m.Type() != n.Type() ) ){
        m.SetError(m.RADIX_ERR, func, 216);
    }
// n has two or under figures including the case |n| = 1.
    if( (n.Head() <= 1u) && DivByShort(m, n, result) ) return result;
//The registration of default division function.
//  if(m.pfLLDiv == NULL) m.UsesKnuthLLDiv();

//Check n = abcd efgh ... 0000 0000 or not.
    if(n.Tail() >= 4u){ //It divides m and n by the power of radix.
//The quotient of 1234567/12000 can be obtained by 1234/12 = 102
//and its remainder 1234567-102*12000=10567.
        SLong mc(m), nc(n);
        int divRdxPow = (int)n.Tail();
    //divide by R^divRdxPow
        mc.MultPowRdx(-divRdxPow);      nc.MultPowRdx(-divRdxPow);
    //recursive call
    //maybe "nc < SlOpMaxValue()"
        result = LLDiv(mc, nc, 0);
        if(!needRem) return result;
    //remainder r=m-n*q
        result.rem = m - result.quot*n;
        if(mc.Verify()) DivVerify(m, n, result);
        return result;
    }

    SLong M(Labs(m)), N(Labs(n));   // M = |m|, N = |n|
/*
It returns the result.
About the relations between quotient and remainder.
 m=n*q+r
If the quotient is defined by the integral division q=m/n, when m<0 and n>0,
q<0 and r<0.
[Example]
When m=-5 and n = 4, q = -5/4=-1 and r = -1.
    -5 = 4*(-1)+ (-1)
Then the remainder has the same sign as that of m.
    q = 5/(-2) = -2
    r = 5 - (-2)*(-2) = 1 > 0
    5 = (-2)*(-2) + 1
*/
// cout << M.llDivMode << "in LLDiv" << endl;
    if(M.llDivMode & M.SetByUser) {
        result = (M.llDivMode & M.Newton) ? M.NewtonLLDiv(M, N, needRem) : M.KnuthLLDiv(M, N, needRem);
    } else {
        M.llDivMode = M.NewtonLLDivIsFaster(M, N) ? M.Newton : M.Knuth;
        result = (M.llDivMode == M.Newton) ? M.NewtonLLDiv(M, N, needRem) : M.KnuthLLDiv(M, N, needRem);
    }

// cout << M.llDivMode << "in LLDiv" << endl;
    if(sgn < 0) result.quot.SetSign(-1);    // result.quot = -result.quot
    if(m.Sign() < 0) result.rem.ChangeSign(216);//It allows the case that rem==0.-0=0
    // result.rem = -result.rem
// check m = q*n + r
    if(M.Verify()) DivVerify(m, n, result);
    return result;
}
// 217
SLong LLDiv(const SLong& m, const SLong& n) {
    Ldiv_t r = LLDiv(m, n, 0);
    return r.quot;
}